%% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
%% Kapitel 2:
%% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\chapter{Overview of Segmentation Methodology} \label{chap:Overview of Segmentation Methodology}

Signal stationarity plays a vital role in many signal processing applications. Information about signal stationarity is necessary, either because most standard algorithms use it as a pre-requisite or because it's segmentation provides specific informations. In many applications detection of stationarity change point is a pre-requisite for parameter extraction. We consider a problem of how to detect this stationarity change point, which violates the signal stationarity. In our case, for Land Mobile Satellite (LMS) received signal parameter extraction requires information about signal stationarity change points. 

This problem is often refered as a Time-Series analysis or more precisely change point detection. The problem of detecting changes in the underlying process (structures) is known as change point detection. In signal processing, the change detection is known as automatic decompositions of received signal to the stationary or weakly stationary parts or segments \cite{B_N_1993}. 

The problem of identification of states can be thought of as segmenting a LMS measured time-series. The idea of segmentation is to devide received time-series into stationary or weakly stationary intervals. segmentation is part of change detection since there is likeli change points between the intervals. In short, segmentation of received time-series into stationary intervals involves identifying the time points at which change occurs. 

Change detection in time-series is refered as a pre-processing step for many signal processing areas. When change detection is performed manually, it is not only exremely slow but also inconsistent. Inconsistent detection can have a adverse affects on the performance of the system. 

In some statistical approaches change detection is often isolated in two parts, \emph{detection} (whether a change exists) and \emph{isolation} (location of the change point). The wide variety of the settings available for change detection techniques. 


\section{Change Classification}

Change detection problem can be classified in two main diffrenet classes.


\begin{description}
\item[Additive change detection] \hfill \\ Additive change detection can be refered as detection of any changes in the mean value of the sequence of observations. It is assumed that additive changes occur in the mean value of input, and thus does not affect the dynamics of the system.
\item[Nonadditive or spectral change detection] \hfill \\ Nonadditive or spectral change detection can be refered as any change in the variance, correlation, spectral characteristics, dynamics of the signal or systems. These changes can also identified as multiplicative changes. Nonaddative changes can affect the dynamics of the systems and thus requires complex change detection methods. 
\end{description}

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.95\columnwidth]{./bilder/Change_Type.pdf}
\end{center}
\caption{Types of changes}
\label{fig:Types of changes}
\end{figure}

Most change detection problems can be classified using one of these two types of problem or using both.

For LMS channel Nonadditive change detection contains two types of changes in the spectral properties:

\begin{itemize} 
\item Multipath change
\item Standard deviation change
\end{itemize}



For modelling the detection tool for change in mean and variance, information about change generation model is necessary. More general mean and variance change generation models shown below in Figure ~\ref{fig:Reference change generation model for change detection}, which will be usefull for designing change detection block diagram.


\tikzstyle{block} = [draw, fill=blue!20, rectangle, text width=3em, text centered, minimum height=3em, minimum width=6em]
\tikzstyle{sum} = [draw, fill=blue!20, circle, node distance=1cm]
\tikzstyle{input} = [coordinate, text width=3em, text centered]
\tikzstyle{output} = [coordinate, text width=3em, text centered]
\tikzstyle{pinstyle} = [pin edge={to-, thin,black}]

\begin{figure}[htbp]
\begin{subfigure}[b]{0.8\textwidth}
\centering

% The block diagram code is probably more verbose than necessary
\begin{tikzpicture}[auto, node distance=3cm,>=latex']\label{fig: Non-parametric change detection}
    % We start by placing the blocks
    \node [input, name=input] {};
    \node [sum, right of=input, pin={[pinstyle] below:$V_t$}, node distance=3cm] (sum) {+};
    \node [block, right of=sum] (Filter) {System $\bm{\tau}$};
    \node [output, right of=Filter] (output) {};
 %   \coordinate [below of=u] (tmp);
    
		\draw [draw,->] (input) -- node[text centered] {$\theta_t = \begin{cases} \theta_0 \\ \theta_1 \end{cases}$} (sum);
		\draw [draw,->] (sum) -- node[text centered] {$\theta_t + V_t$} (Filter);
		\draw [->] (Filter) -- node[text centered] [name=y] {$Y_t$}(output);
    
    \end{tikzpicture}


\caption{Additive change generation model}
\label{fig:Additive change generation model}
\end{subfigure}\\ \\


\begin{subfigure}[b]{0.8\textwidth}
\centering

% The block diagram code is probably more verbose than necessary
\begin{tikzpicture}[auto, node distance=3cm,>=latex']\label{fig: Non-parametric change detection}
    % We start by placing the blocks
    \node [input, name=input] {};
    \node [sum, right of=input, pin={[pinstyle] below:$V_t$}, node distance=3cm] (sum) {$\times$};
    \node [block, right of=sum] (Filter) {System $\bm{\tau}$};
    \node [output, right of=Filter] (output) {};
%    \coordinate [below of=u] (tmp);
    
		\draw [draw,->] (input) -- node[text centered] {$\theta_t = \begin{cases} \theta_0 \\ \theta_1 \end{cases}$} (sum);
		\draw [draw,->] (sum) -- node[text centered] {$\theta_t V_t$} (Filter);
		\draw [->] (Filter) -- node[text centered] [name=y] {$Y_t$}(output);
    
    \end{tikzpicture}

\caption{Variance change generation model}
\label{fig:Variance change generation model}
\end{subfigure}
\caption{Reference change generation model for change detection \cite{B_N_1993}}
\label{fig:Reference change generation model for change detection}
\end{figure}



where, $y_t$ is the received measurement at time instant $t$, $\theta_t$ is deterministic component and $V_t$ represents the additive white noise. In this change generation diagram $\theta$ can be refered as change in parameters based on that received signal contains change in mean or change in variance characteristics.

In our case, LMS received signal contains both types of changes (additive and nonadditive). These problem can be classified as change detection in two steps.

LMS signal stationarity analysis can be done in following steps: -

\begin{itemize}
\item Detect additive change in the received signal and define segment borders.
\item Detect nonadditive changes in the previously calculated segments.
\end{itemize}

The process is much more clear after the defining the change detection methods in details.

Taxonomy is required to get the impression of the different change detection algorithm. Next section presents the taxonomy of the change detection algorithms.


\section{Stationarity Change Detection Algorithms Taxonomy}

Figure ~\ref{fig:Taxonomy of change detection approaches} shows the taxonomy to classify the change detection approaches. There are various other approaches are also available for change detection, but we are only considering below mentioned approaches in our work. For discussion we will use change detection taxonomy shown in Figure ~\ref{fig:Taxonomy of change detection approaches}. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.95\columnwidth]{./bilder/change_detection.pdf}
\end{center}
\caption{Taxonomy of change detection approaches}
\label{fig:Taxonomy of change detection approaches}
\end{figure}

Stationarity change detection problems can be classified in main two classes of problems based on it's practical requirements. Below we list two common change detection classes.

%\begin{description}

\subsection{Online Change Detection}

The objective is to detect changes as soon as possible immediately after it occurs. Detection of change times is done based on all or certain past data. Stopping alarm is given at the time when there is sufficient evidence of change is occured in signal statistics. 

This technique is inteneded to detect a change in incoming data at particular rate. The goal is to detect changes with minimum delay and minimum false alarm rate. Some online change detection techniques are identified sequential change detection, increamnetal change detection, etc.

One type of online change detections are Statistical Parameter Change Detection, which is briefly explained below.


\subsubsection{Statistical Parameter Change Detection} 

Statistical parameter change according to it's name, this approach looks for change in the parameters of the underlying distribution. In this approach Time-Series is assumed to follow particular distribution and we are trying to detect any drift or change from known distribution. 

These approaches have the following characteristics \cite{S_thesis_2010}

\begin{itemize}

\item Assumption is that data follows parametric distribution.

\item Data contains the point where the undelying parametric distribution changes.

\item Idea is to detect the parametric distribution change points and sometimes the parameters before and after the change points.

\end{itemize}



\subsection{Off-line Change Detection} 

This algorithms are designed to collect entire data from the measurements. Change detection Algorithms are applied on the collected data set to detect whether there is change or not and this step is known as \emph{detection}. 

If there is change available, these approch try to locate the change location known as \emph{isolation}. The goal is to check whether signal characteristics are changed. This characteristics can be classified according to mean, variance, correlation structure, spectral properties. sometimes off-line change detection problem is refered as segmentation.

In our report, we discuss the two types of the off-line change detection approaches.

\subsubsection{Segmentation}

LMS channel contains various type of environment and due to that there is high probability of the loss of the stationarity. Segmentation is refered as the identification of the points in received data, where non-stationary behaviours are occured.

The goal of the segmentation approach is to segment the Time-Series in k different segments, which is stationary or weakly stationary. Segmentation approach requires the user defined inputs such as thresholds or number of segments etc.

Segmentation approach requires the following information\cite{S_thesis_2010}:

\begin{itemize}

\item \emph{Stopping Condition}: used to get information about the optimal number of segments. After achieving optimal number of segments from the dataset further segmentation can be stopped. These parameters are method dependent not operation dependent.

\item \emph{Model}: For calculation of the segments using segmentation methods the assumption about the underlying model should be required. Model is selected based on the fitting to the measured received data. Some approach extensively depend on the model, so inaccurate selection of the model lead to the more false segments.

\end{itemize}

\subsubsection{Clustering}


Clustering is defined as grouping together the similar data items to cluster. Goal of the clustering is to partition data $\bm{Y}$ into $k$ clusters. For accuracy, this approach requires the previous information about the distribution of data. 

Clustering is very well known approach for detection of the change in the received signal characteristics in signal processings. For LMS channel 'K-means' and 'Fuzzy C-means' are well known segmentation approaches \cite{M_2011}. Complexity of these algorithms are increased with increase in the number of clustes.

Overview of the K-means and Fuzzy C-means approaches: 

\begin{description}

\item [\emph{K-means}] \hfill \\ The K-means algorithm, probably the first one of the clustering algorithms proposed, is based on a very simple idea: Given a set of initial clusters, assign each point to one of them, then each cluster center is replaced by the mean point on the respective cluster. These two simple steps are repeated until convergence.

\item [\emph{Fuzzy C-means}] \hfill \\ The goal of traditional clustering is to assign each data point to one and only one cluster. In contrast, fuzzy clustering assigns different degrees of membership to each point. The membership of a point is thus shared among various clusters. This creates the concept of fuzzy boundaries which differs from the traditional concept of well-defined boundaries.

\end{description}

 
Online and offline both approaches contains additive and nonadditive change detection techniques, which will be covered later in this report. Future chapters also presents the detailed description about each blocks. Next section includes the general operational methodology of the change detection algorithms.


\section{Change Detection Operational Blocks}

In general, change detection approaches are classified as the series of operations, feature extraction, change detection, and validation, illustrated in Figure ~\ref{fig:General change detection methodology}. 

In the feature extraction phase, the LMS received signal is converted into a representation, which is more useful for change detection. This is the place where dimensionality reduction occurs, where received signal dimension is extermely high. This portion contains various pre-processing filters, which is applied on received signal in order to reduce noise and improve the change detection results. In our case, sometimes addressed as a fast fading removal.



\tikzstyle{block} = [draw, fill=blue!20, rectangle, text width=5em, text centered, minimum height=3em, minimum width=6em]
\tikzstyle{sum} = [draw, fill=blue!20, circle, node distance=1cm]
\tikzstyle{input} = [coordinate, text width=5em, text centered]
\tikzstyle{output} = [coordinate, text width=5em, text centered]
\tikzstyle{pinstyle} = [pin edge={to-,very thick,black}]

\begin{figure}[h]
% The block diagram code is probably more verbose than necessary
\begin{tikzpicture}[auto, node distance=3cm,>=latex']\label{fig: Non-parametric change detection}
    % We start by placing the blocks
    \node [input, name=input] {};
    \node [block, right of=input] (Feature Extraction) {Feature Extraction};
    \node [block, right of=Feature Extraction, node distance=5cm] (Change Detection) {Change Detection};
    
    \draw [->] (Feature Extraction) -- node[text width=5em, text centered] {Extracted Parameters} (Change Detection);
    \node [block, right of=Change Detection, node distance=4.5cm] (Validation) {Validation};
    \draw [->] (Change Detection) -- node [name=u] {Segments} (Validation);
    \node [output, right of=Validation] (output) {};
    \coordinate [below of=u] (tmp);
    
		\draw [draw,->] (input) -- node[text width=5em, text centered] {Received Signal} (Feature Extraction);
		\draw [->] (Validation) -- node[text width=5em, text centered] [name=y] {Segments}(output);
		\draw [->] (Validation) |-(tmp)-| node[near end] {Error} (Change Detection);
		
    
\end{tikzpicture}
\caption{General change detection methodology}
\label{fig:General change detection methodology}
\end{figure}


In change detection phase, various change detection methods are applied on the received signal and received signal is segmented based on it. The majority of this report deals with various methods that can be used in this step. 

In the final phase, the validation is applied. The result of the validation can then be compared to some optimal results to calculate an error. This error can be passed back to the change detection phase to improve the performance. Validation becomes trivial in most of the sequential change detection algorithms. Validation is effective in batch processing application. 

This phases can be modified in the next chapters according to change detection methods, but general block diagram presents sufficient overview of the change detection algorithms.




\section{Signal Model for change detection}

LMS received signal contains the multipath components. As discussed before LMS signal contains the two types of changes. As proposed in \cite{L_1991}, LMS received signal at mobile terminal experience the multiplicative fading. If the LMS mobile terminal is in the non-LOS condition and specular reflected component is opposite phase then received signal face the mean change in the signal. 

LMS propogation channel can be represented in three different states direct ray, specular reflected component and multipath component \cite{M_2011}. Acoording to \cite{FVC_2001} LMS channel can be represented as the shown below:

	\begin{equation}\label{eq:LMS channel model}
	\begin{aligned}
	h(t, \tau) = \sum a_i \delta(\tau - \tau_i(t))
	\end{aligned}
	\end{equation}
	
	This means that different paths are treated as delta function affected by attenuations, phase shifts and delay which are time varying as indicated by above equation \cite{FVC_2001}.

Wireless channel can be modelled with Auto Regressive (AR) model as presented in \cite{filteri}. Also according to paper \cite{L_1991} \cite{SK_2012}, the fading component can be seen as a multiplicative to the direct transmitted signal.

For change detection, we use AR model as signal model of LMS received signal. AR model is contains change in mean and change in variance problem. AR model is widely used for modelling speech signal, geological signal, biological signal, etc.

Approximation of LMS channel with AR model enables the use of adaptive filtering and change detection approaches. 

We assume that there exists certain conditional probability density function $p_{\theta}(y_t/Y_1^{t-1})$, which serves as model for the observed data \cite{B_N_1993}. The problem is to detect change in the vector parameter $\theta$. AR model is described by the following equation:

	\begin{equation}\label{eq:AR(p) model}
	\begin{aligned}
	y(t) = \sum_{k=1}^{p} a(k) y({t-k}) + w(t)
	\end{aligned}
	\end{equation}

Here, $a(k)$ is the AR parameters, $w(t)$ is the zero mean additive white gaussian noise with unit variance. The observed sequence has a conditional probability density of $p_{\theta}(y(t)/Y_1^{t-1})$. Parameter $\theta$ contains AR coefficients and standard deviation of the observed signal. Our main goal is to detect change in the parameter $\theta$, when it changes $\theta_0$ to $\theta_1$.

